{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Element IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #binary-search #sorting #monotonic-stack #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #二分查找 #排序 #单调栈 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: secondGreaterElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个更大元素 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的非负整数数组&nbsp;<code>nums</code>&nbsp;。对于&nbsp;<code>nums</code>&nbsp;中每一个整数，你必须找到对应元素的&nbsp;<strong>第二大</strong>&nbsp;整数。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>nums[j]</code>&nbsp;满足以下条件，那么我们称它为&nbsp;<code>nums[i]</code>&nbsp;的&nbsp;<strong>第二大</strong>&nbsp;整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>j &gt; i</code></li>\n",
    "\t<li><code>nums[j] &gt; nums[i]</code></li>\n",
    "\t<li>恰好存在 <strong>一个</strong>&nbsp;<code>k</code>&nbsp;满足 <code>i &lt; k &lt; j</code>&nbsp;且&nbsp;<code>nums[k] &gt; nums[i]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果不存在&nbsp;<code>nums[j]</code>&nbsp;，那么第二大整数为&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，数组&nbsp;<code>[1, 2, 4, 3]</code>&nbsp;中，<code>1</code>&nbsp;的第二大整数是&nbsp;<code>4</code>&nbsp;，<code>2</code>&nbsp;的第二大整数是&nbsp;<code>3</code>&nbsp;，<code>3</code> 和&nbsp;<code>4</code>&nbsp;的第二大整数是&nbsp;<code>-1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数数组<em>&nbsp;</em><code>answer</code>&nbsp;，其中<em>&nbsp;</em><code>answer[i]</code>是<em>&nbsp;</em><code>nums[i]</code>&nbsp;的第二大整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,4,0,9,6]\n",
    "<b>输出：</b>[9,6,6,-1,-1]\n",
    "<strong>解释：</strong>\n",
    "下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。\n",
    "下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。\n",
    "下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。\n",
    "下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。\n",
    "下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。\n",
    "所以我们返回 [9,6,6,-1,-1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3]\n",
    "<b>输出：</b>[-1,-1]\n",
    "<strong>解释：</strong>\n",
    "由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-element-iv](https://leetcode.cn/problems/next-greater-element-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-element-iv](https://leetcode.cn/problems/next-greater-element-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,0,9,6]', '[3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        st1 = []\n",
    "        st2 = []\n",
    "        def lower_bound(arr, x):\n",
    "            l, r = 0, len(arr)\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if nums[arr[mid]] <= x:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l \n",
    "        ans = [-1] * n \n",
    "        for i in range(n-1, -1, -1):\n",
    "            tmp = []\n",
    "            while st1 and nums[st1[-1]] <= nums[i]:\n",
    "                tmp.append(st1.pop())\n",
    "            m = len(tmp)\n",
    "\n",
    "            idx1 = idx2= float('inf')\n",
    "            if len(st1) > 1:\n",
    "                idx1 = st1[-2] \n",
    "            if st2:\n",
    "                t = lower_bound(st2, nums[i]) - 1\n",
    "                if t >= 0:\n",
    "                    idx2 = st2[t]\n",
    "            if idx1 < idx2:\n",
    "                ans[i] = nums[idx1] \n",
    "            elif idx2 < float('inf'):\n",
    "                ans[i] = nums[idx2]\n",
    "            else:\n",
    "                ans[i] = -1 \n",
    "            st1.append(i)\n",
    "            for j in range(m-1, -1, -1):\n",
    "                while st2 and nums[st2[-1]] <= nums[tmp[j]]:\n",
    "                    st2.pop() \n",
    "                st2.append(tmp[j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        ans=[-1]*len(nums)\n",
    "        hpBuffer,monoStack=list(),list()\n",
    "        for i,num in enumerate(nums):\n",
    "            while hpBuffer and hpBuffer[0][0]<num:\n",
    "                ans[heapq.heappop(hpBuffer)[1]]=num\n",
    "            while monoStack and nums[monoStack[-1]]<num:\n",
    "                idx=monoStack.pop()\n",
    "                heapq.heappush(hpBuffer,(nums[idx],idx))\n",
    "            monoStack.append(i)\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        stack = [0]\n",
    "        mark = ['l']\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[stack[-1]]:\n",
    "                stack.append(i)\n",
    "                mark.append('l')\n",
    "            else:\n",
    "                temp = []\n",
    "                while len(stack) > 0 and nums[stack[-1]] < nums[i]:\n",
    "                    num = stack.pop()\n",
    "                    m = mark.pop()\n",
    "                    if m == 'l':\n",
    "                        temp.append(num)\n",
    "                    else:\n",
    "                        ans[num] = nums[i]\n",
    "                stack.append(i)\n",
    "                mark.append('l')\n",
    "                for j in range(len(temp) - 1, -1, -1):\n",
    "                    stack.append(temp[j])\n",
    "                    mark.append('r')\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st, q = [], []\n",
    "        ans = [-1] * len(nums)        \n",
    "        for i, x in enumerate(nums):\n",
    "            # 堆中是栈弹出的，已经拥有一个更大的数\n",
    "            while q and q[0][0] < x: # 再次找到一个更大的数\n",
    "                ans[heappop(q)[1]] = x\n",
    "            while st and nums[st[-1]] < x:\n",
    "                # x 是栈顶第一个更大的数,暂时放入堆。\n",
    "                j = st.pop()\n",
    "                heappush(q, (nums[j], j))\n",
    "            st.append(i)        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        q = []\n",
    "        res = [-1] * len(nums)\n",
    "        \n",
    "        for i, v in enumerate(nums):\n",
    "            while len(q) > 0 and q[0][0] < v:\n",
    "                res[q[0][1]] = v\n",
    "                heappop(q)\n",
    "                \n",
    "            while len(st) > 0 and nums[st[-1]] < v:\n",
    "                heappush(q, (nums[st[-1]], st[-1]))\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        st, h = deque(), []\n",
    "        import heapq\n",
    "        for i, num in enumerate(nums):        \n",
    "            while h and h[0][0] < num:\n",
    "                _, j = heapq.heappop(h)\n",
    "                res[j] = num\n",
    "            while st and num > nums[st[-1]]:\n",
    "                j = st.pop()\n",
    "                heapq.heappush(h, (nums[j], j))\n",
    "            st.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        nxt_dict = {}\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack2 and nums[stack2[-1]] < num:\n",
    "                nxt_dict[stack2.pop()] = i\n",
    "            temp = []\n",
    "            while stack1 and nums[stack1[-1]] < num:\n",
    "                temp.append(stack1.pop())\n",
    "            while temp:\n",
    "                stack2.append(temp.pop())\n",
    "            stack1.append(i)\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            j = nxt_dict.get(i, -1)\n",
    "            if j < 0:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(nums[j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 比当前元素更大的元素\n",
    "# class Solution:\n",
    "#     def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        # t = []\n",
    "        # ans=[-1]*len(nums)\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     while t and nums[t[-1]]<num:\n",
    "        #         ans[t.pop()]=num\n",
    "        #     t.append(i)\n",
    "        # print(ans)\n",
    "#\n",
    "\n",
    "# 下一个更大的元素\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s, t = [], []\n",
    "        ans=[-1]*len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            while t and nums[t[-1]]<num:\n",
    "                # ans[t.pop()]=num\n",
    "                idx = t.pop()\n",
    "                ans[idx]=num\n",
    "            # t.append(i)\n",
    "            j=len(s)-1\n",
    "            # 表示最后一个元素\n",
    "            while j >= 0 and nums[s[j]]<num:\n",
    "                j -= 1\n",
    "            t += s[j+1:]\n",
    "            del s[j+1:]\n",
    "            s.append(i)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        #  s存储遍历过的数\n",
    "        #  t存储遍历过，且右侧有比他大的数\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        s, t = [], []\n",
    "        for i, x in enumerate(nums):\n",
    "            while t and nums[t[-1]] < x:\n",
    "                ans[t.pop()] = x\n",
    "            j = len(s) - 1\n",
    "            while j >= 0 and nums[s[j]] < x:\n",
    "                j -= 1\n",
    "            t += s[j + 1:]\n",
    "            del s[j + 1:]\n",
    "            s.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        output = [-1]*n\n",
    "        \n",
    "        # 双单调栈\n",
    "        st1 = []\n",
    "        st2 = []\n",
    "        for i, ele in enumerate(nums):\n",
    "            while st2 and ele > nums[st2[-1]]:\n",
    "                output[st2[-1]] = ele\n",
    "                st2.pop()\n",
    "            tmp = []    \n",
    "            while st1 and ele > nums[st1[-1]]:               \n",
    "                tmp.append(st1.pop())\n",
    "            while tmp:\n",
    "                st2.append(tmp.pop())\n",
    "            st1.append(i)\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans, st1, st2 = [-1] * n, [], []\n",
    "        '''\n",
    "        # 双层遍历\n",
    "        for i in range(0, n):\n",
    "            flag = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] > nums[i]:\n",
    "                    flag += 1\n",
    "                if flag == 2:\n",
    "                    fflag = 1\n",
    "                    ans[i] = nums[j]\n",
    "                    break\n",
    "        return ans\n",
    "        '''\n",
    "        # 双单调栈\n",
    "        for i, x in enumerate(nums):\n",
    "            # 如果新入值大于st2栈顶，则st2栈顶的值的第二个最大值就是x\n",
    "            while st2 and nums[st2[-1]] < x:\n",
    "                ans[st2.pop()] = x\n",
    "            '''\n",
    "            # 该段代码错误在没有保持原有顺序把st1中的数据放进st2\n",
    "            while st1 and nums[st1[-1]] < x:\n",
    "                st2.append(st1.pop())\n",
    "            '''\n",
    "            # 保证顺序放入数据\n",
    "            j = len(st1) - 1\n",
    "            while j >= 0 and nums[st1[j]] < x:\n",
    "                j -= 1\n",
    "            st2 += st1[j + 1:]\n",
    "            del st1[j + 1:]\n",
    "            st1.append(i)\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "            \n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        st1 = deque()\n",
    "        st2 = deque()\n",
    "        ans = [-1] * n  \n",
    "        for i in range(n):\n",
    "            while st2 and nums[st2[-1]] < nums[i]:\n",
    "                ans[st2[-1]] = nums[i]\n",
    "                st2.pop() \n",
    "            arr = deque()\n",
    "            while st1 and nums[st1[-1]] < nums[i]:\n",
    "                arr.appendleft(st1[-1])\n",
    "                st1.pop()\n",
    "            st2.extend(arr)\n",
    "            st1.append(i) \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        ans=[-1]*len(nums)\n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack2 and nums[stack2[-1]]<x:\n",
    "                ans[stack2.pop()]=x   \n",
    "            j=len(stack1)-1\n",
    "            while j>=0 and nums[stack1[j]]<x:\n",
    "                j-=1    \n",
    "            stack2+=stack1[j+1:]\n",
    "            del stack1[j+1:]\n",
    "            stack1.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        t = [-1] * n\n",
    "        st1, st2 = [], []\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            while st2 and nums[st2[-1]] < nums[i]:\n",
    "                ans[st2.pop()] = nums[i]\n",
    "            while st1 and nums[st1[-1]] < nums[i]:\n",
    "                t.append(st1.pop())\n",
    "            st2 += t[::-1]\n",
    "            st1.append(i)\n",
    "            # print(i, st1, st2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        result = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            while s2 and nums[i] > nums[s2[-1]]:\n",
    "                result[s2.pop()] = nums[i]\n",
    "            tmp = []\n",
    "            while s1 and nums[i] > nums[s1[-1]]:\n",
    "                tmp.append(s1.pop())\n",
    "            s2.extend(tmp[::-1])\n",
    "            s1.append(i)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        st1 = []\n",
    "        st2 = []\n",
    "        ans = [-1] * n  \n",
    "        for i in range(n):\n",
    "            while st2 and nums[st2[-1]] < nums[i]:\n",
    "                ans[st2[-1]] = nums[i]\n",
    "                st2.pop() \n",
    "            arr = deque()\n",
    "            while st1 and nums[st1[-1]] < nums[i]:\n",
    "                #arr.insert(0,st1[-1])\n",
    "                arr.appendleft(st1[-1])\n",
    "                st1.pop()\n",
    "            st2 += arr\n",
    "            st1.append(i) \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s, t = [], []\n",
    "\n",
    "        ans = [-1] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            # 当 x 大于 t 栈顶的下标对应数时, 说明 x 是 nums[t[-1]] 的第二大整数\n",
    "            while t and x > nums[t[-1]]:\n",
    "                ans[t.pop()] = x\n",
    "\n",
    "            # 如果倒序遍历, 那么会反转原本的顺序, \n",
    "            # 比如 [12, 0, 12], 在遇见第二个 12 时, s = [0 (12), 1 (0)], 如果选择 pop(),\n",
    "            # 那么 t = [1 (0), 0 (12)], 本应得到 t = [0, 1], \n",
    "            # 因此需要通过变量 j, 得到需要删除的长度, 然后通过切片得到正确的顺序\n",
    "            j = len(s) - 1\n",
    "            while j >= 0 and s and x > nums[s[j]]:\n",
    "                j -= 1\n",
    "            # t 记录 nums 右端有一个大于的整数的 数下标\n",
    "            t += s[j+1:]\n",
    "            del s[j+1:]     # 需要从 s 中删除的下标\n",
    "            s.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        ans, s, t = [-1] * len(nums), [], []\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            while t and nums[t[-1]] < x:\n",
    "\n",
    "                ans[t.pop()] = x\n",
    "\n",
    "            j = len(s) - 1\n",
    "\n",
    "            while j >= 0 and nums[s[j]] < x:\n",
    "\n",
    "                j -= 1\n",
    "\n",
    "            t += s[j + 1:]\n",
    "\n",
    "            del s[j + 1:]\n",
    "\n",
    "            s.append(i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        ans, s, t = [-1] * len(nums), [], []\n",
    "        for i, x in enumerate(nums):\n",
    "            while t and nums[t[-1]] < x:\n",
    "                ans[t.pop()] = x\n",
    "            j = len(s) - 1\n",
    "            while j >= 0 and nums[s[j]] < x:\n",
    "                j -= 1\n",
    "            t += s[j+1:]\n",
    "            del s[j+1:]\n",
    "            s.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\r\n",
    "        ans, s, t = [-1] * len(nums), [], []\r\n",
    "\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            while t and nums[t[-1]] < x:\r\n",
    "                ans[t.pop()] = x\r\n",
    "\r\n",
    "            j = len(s) - 1\r\n",
    "            while j >= 0 and nums[s[j]] < x:\r\n",
    "                j -= 1\r\n",
    "            t += s[j + 1 :]\r\n",
    "            del s[j + 1 :]\r\n",
    "            s.append(i)\r\n",
    "\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st0, st1 = [], []\n",
    "        ans = [-1] * len(nums)\n",
    "        for i, n in enumerate(nums):\n",
    "            while st1 and n > nums[st1[-1]]:\n",
    "                j = st1.pop()\n",
    "                ans[j] = n\n",
    "            tmp = len(st1)\n",
    "            while st0 and n > nums[st0[-1]]:\n",
    "                st1.insert(tmp, st0.pop())\n",
    "            st0.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        st = []\n",
    "        pq = PriorityQueue()\n",
    "        for i,num in enumerate(nums):\n",
    "            while not pq.empty() and pq.queue[0][0] < num:\n",
    "                _,x = pq.get()\n",
    "                ans[x] = num\n",
    "            while st and nums[st[-1]] < num:\n",
    "                pq.put((nums[st[-1]], st[-1]))\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 单调递减栈 是找到了一个右侧比它大的数,就弹出这个数\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        t = deque([])\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            while t and nums[t[-1]] < num:\n",
    "                j = t.pop()\n",
    "                ans[j] = num\n",
    "            j = len(stack) - 1\n",
    "            while j >= 0 and nums[stack[j]] < num:\n",
    "                j -= 1\n",
    "            t += stack[j+1:]\n",
    "            del stack[j+1:]\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        stk,minheap=[],[]\n",
    "        res=[-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while minheap and nums[i]>minheap[0][0]:\n",
    "                res[minheap[0][1]]=nums[i]\n",
    "                heappop(minheap)\n",
    "            while stk and nums[i]>nums[stk[-1]]:\n",
    "                heappush(minheap,(nums[stk[-1]],stk[-1]))\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        stk, heap = [], []\n",
    "        ans = [-1] * len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            while heap and num > heap[0][0]:\n",
    "                _, j = heappop(heap)\n",
    "                ans[j] = num\n",
    "            while stk and num > nums[stk[-1]]:\n",
    "                j = stk.pop()\n",
    "                heappush(heap, (nums[j], j))\n",
    "            stk.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        stk, heap = [], []\n",
    "        ans = [-1] * len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            while heap and num > heap[0][0]:\n",
    "                _, j = heappop(heap)\n",
    "                ans[j] = num\n",
    "            while stk and num > nums[stk[-1]]:\n",
    "                j = stk.pop()\n",
    "                heappush(heap, (nums[j], j))\n",
    "            stk.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack1 and stack1[0][0] < nums[i]:\n",
    "                ind1 = heapq.heappop(stack1)[1]\n",
    "                res[ind1] = nums[i]\n",
    "            while stack2 and nums[stack2[-1]] < nums[i]:\n",
    "                ind2 = stack2.pop()\n",
    "                heapq.heappush(stack1, (nums[ind2], ind2))\n",
    "            stack2.append(i)\n",
    "            # print(res, stack1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        heap = []\n",
    "        ans = [-1] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while heap and num > heap[0][0]:\n",
    "                _, idx = heapq.heappop(heap)\n",
    "                ans[idx] = num\n",
    "            \n",
    "            while stack and num > nums[stack[-1]]:\n",
    "                t = stack.pop()\n",
    "                heapq.heappush(heap, (nums[t], t))\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        stack,queue = [],[]\n",
    "        for i,j in enumerate(nums):\n",
    "            while queue and queue[0][0] < j:\n",
    "                # 队首被弹出意味着找到了第二个比他大的值\n",
    "                pre = heappop(queue)[1]\n",
    "                ans[pre] = j\n",
    "            while stack and nums[stack[-1]] < j:\n",
    "                # 栈中元素被弹出意味着找到了第一个比他大的元素\n",
    "                cur = stack.pop()\n",
    "                heappush(queue,[nums[cur],cur])\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        q = []\n",
    "        res = [-1] * len(nums)\n",
    "        \n",
    "        for i, v in enumerate(nums):\n",
    "            while len(q) > 0 and q[0][0] < v:\n",
    "                res[q[0][1]] = v\n",
    "                heappop(q)\n",
    "                \n",
    "            while len(st) > 0 and nums[st[-1]] < v:\n",
    "                heappush(q, (nums[st[-1]], st[-1]))\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans, stk, pq = [-1] * n, [], []\n",
    "        for i, x in enumerate(nums):\n",
    "            while pq and x > pq[0][0]:\n",
    "                ans[heappop(pq)[1]] = x\n",
    "            while stk and x > nums[stk[-1]]:\n",
    "                heappush(pq, [nums[stk[-1]], stk.pop()])\n",
    "            stk.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque \n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s1, s2 = [ ],[ ]\n",
    "        dic = { }\n",
    "        for j in range( len( nums )) :\n",
    "            while s2 and ( nums[j] > nums[ s2[-1]  ] ) :\n",
    "                tmp = s2.pop( )\n",
    "                dic[ tmp ] = j  \n",
    "            tmp = [ ]\n",
    "            while  s1 and  ( nums[j] > nums[ s1[-1] ] ) : \n",
    "                i = s1.pop( ) \n",
    "                tmp.append( i )\n",
    "            s2 += tmp[::-1 ] \n",
    "            s1.append( j )\n",
    "        ans=[]\n",
    "        for j in range( len( nums )) :\n",
    "            if j in dic:\n",
    "                ans.append( nums[ dic[j ]]) \n",
    "            else:\n",
    "                ans.append( -1 )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        from heapq import heappop, heappush\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        mono_stack, hp = [], []\n",
    "        for i, x in enumerate(nums):\n",
    "            while hp and hp[0][0] < x:\n",
    "                pos = heappop(hp)[1]\n",
    "                ans[pos] = x\n",
    "\n",
    "            while mono_stack and nums[mono_stack[-1]] < x:\n",
    "                cur = mono_stack.pop()\n",
    "                heappush(hp, [nums[cur], cur])\n",
    "            mono_stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = [-1] * n\n",
    "        \n",
    "        ones = SortedList()\n",
    "        zeros = SortedList()\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            idx = ones.bisect_left((num, -1))\n",
    "            for _ in range(idx):\n",
    "                ret[ones[0][1]] = num\n",
    "                ones.remove(ones[0])\n",
    "            idx = zeros.bisect_left((num, -1))\n",
    "            for _ in range(idx):\n",
    "                ones.add(zeros[0])\n",
    "                zeros.remove(zeros[0])\n",
    "            zeros.add((num, i))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        first_stack = []\n",
    "        second_stack = []\n",
    "        N = len(nums)\n",
    "        answer = [-1] * N\n",
    "        for i, n in enumerate(nums):\n",
    "            while second_stack and second_stack[-1][0] < n:\n",
    "                _, j = second_stack.pop()\n",
    "                answer[j] = n\n",
    "            tmpl = []\n",
    "            while first_stack and first_stack[-1][0] < n:\n",
    "                tmpl.append(first_stack.pop())\n",
    "            second_stack.extend(reversed(tmpl))\n",
    "            first_stack.append((n, i))\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        res = [-1 for i in range(len(nums))]\n",
    "        for i,num in enumerate(nums):\n",
    "            # print(stack1,stack2)\n",
    "            while stack2 and stack2[-1][0]<num:\n",
    "                _num,j = stack2.pop()\n",
    "                res[j] = num\n",
    "            tmp = []\n",
    "            while stack1 and stack1[-1][0]<num:\n",
    "                tmp.append(stack1.pop())\n",
    "            while tmp:\n",
    "                stack2.append(tmp.pop())\n",
    "            stack1.append((num,i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: list[int]) -> list[int]:\n",
    "        lis1 = []\n",
    "        lis2 = []\n",
    "        res = [-1] * len(nums)\n",
    "        for index, item in enumerate(nums):\n",
    "            while len(lis2) > 0:\n",
    "                num = heapq.heappop(lis2)\n",
    "                if item > num[0]:\n",
    "                    res[num[1]] = item\n",
    "                else:\n",
    "                    heapq.heappush(lis2, num)\n",
    "                    break\n",
    "\n",
    "            while len(lis1) > 0:\n",
    "                num = heapq.heappop(lis1)\n",
    "                if item > num[0]:\n",
    "                    heapq.heappush(lis2, num)\n",
    "                else:\n",
    "                    heapq.heappush(lis1, num)\n",
    "                    break\n",
    "            heapq.heappush(lis1, (item, index))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        queue = []\n",
    "        for i , num in enumerate(nums):\n",
    "            tmp = []\n",
    "            while queue:\n",
    "                x , idx , cnt = heapq.heappop(queue)\n",
    "                if num > x:\n",
    "                    print(x,num,cnt)\n",
    "                    cnt += 1\n",
    "                    if cnt >= 2:\n",
    "                        res[idx] = num\n",
    "                        continue\n",
    "                    tmp.append((x,idx,cnt))\n",
    "                else:\n",
    "                    tmp.append((x,idx,cnt))\n",
    "                    break\n",
    "            if tmp:\n",
    "                for x in tmp:\n",
    "                    heapq.heappush(queue,x)\n",
    "\n",
    "            heapq.heappush(queue,(num,i,0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        A = [-1 for _ in range(n)]\n",
    "        sa = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while sa and x > sa[0][0]:\n",
    "                A[sa[0][1]] = i\n",
    "                del sa[0]\n",
    "            while stack and x > stack[-1][1]:\n",
    "                j, y = stack.pop()\n",
    "                bisect.insort(sa, (y, j))\n",
    "            stack.append((i, x))    \n",
    "        return [nums[x]if x != -1 else -1 for x in A]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        temp = list(sorted(zip(range(n), nums), reverse = True, key = lambda x:x[1]))\n",
    "        ans = [-1]*n\n",
    "        # print(temp)\n",
    "        bi = []\n",
    "        for i in range(n):\n",
    "            idx = bisect.bisect_right(bi,temp[i])\n",
    "            if idx<len(bi)-1:\n",
    "                ans[temp[i][0]] = bi[idx+1][1]\n",
    "            bisect.insort(bi,temp[i])\n",
    "            # print(ans,bi)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        st = []\n",
    "        e = [[] for _ in range(n)]\n",
    "        pos = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            a = e[i]\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                a.append(nums[st.pop()])\n",
    "            if st:\n",
    "                k = st[-1]\n",
    "                a.append(nums[k])\n",
    "                b = e[k]\n",
    "                x = pos[k]\n",
    "                while x < len(b) and b[x] <= nums[i]:\n",
    "                    x += 1\n",
    "                if x < len(b):\n",
    "                    res[i] = b[x]\n",
    "                pos[k] = x\n",
    "            st.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        st = []\n",
    "        e = [[] for _ in range(n)]\n",
    "        pos = [0 for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                e[i].append(nums[st.pop()])\n",
    "            if st:\n",
    "                k = st[-1]\n",
    "                e[i].append(nums[k])\n",
    "                ar = e[k]\n",
    "                x = pos[k]\n",
    "                while x < len(ar) and ar[x] <= nums[i]:\n",
    "                    x += 1\n",
    "                if x < len(ar):\n",
    "                    res[i] = ar[x]\n",
    "                pos[k] = x\n",
    "            st.append(i)\n",
    "        return res\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        sl = SortedList()\n",
    "        n = len(nums)\n",
    "        cnt = [0] * n\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            sl.add((x, i))\n",
    "\n",
    "            dels = []\n",
    "            for y, j in sl:\n",
    "                if y >= x: break\n",
    "                cnt[j] += 1\n",
    "                if cnt[j] == 2:\n",
    "                    ans[j] = x\n",
    "                    dels.append((y, j))\n",
    "\n",
    "            for p in dels:\n",
    "                sl.remove(p)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        zeros = [] # [val, idx]\n",
    "        ones = [] # [val, idx]\n",
    "        result = [-1] * len(nums)\n",
    "        for i,n in enumerate(nums):\n",
    "            while ones and ones[0][0] < n:\n",
    "                val, idx = heappop(ones)\n",
    "                result[idx] = n\n",
    "            while zeros and zeros[0][0] < n:\n",
    "                heappush(ones, heappop(zeros))\n",
    "            heappush(zeros, [n,i])\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        k = 2\n",
    "        sl = SortedList()\n",
    "        lst = sorted([(x, -i) for i, x in enumerate(nums)])\n",
    "        ans = [-1] * len(nums)\n",
    "        for x, i in lst[::-1]:\n",
    "            t = sl.bisect_left(i)\n",
    "            if t >= k:\n",
    "                ans[-i] = nums[-sl[t-2]]\n",
    "            sl.add(i)\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        queue = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            while len(queue) and queue[-1][1] < num:\n",
    "                ans[queue.pop()[0]] = num\n",
    "            pos = len(stack) - 1\n",
    "            while pos >= 0 and stack[pos][1] < num:\n",
    "                pos -= 1\n",
    "            queue += stack[pos + 1:]\n",
    "            del(stack[pos + 1:])\n",
    "            stack.append([idx, num])\n",
    "            # print(queue)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        heap_0 = []\n",
    "        heap_1 = []\n",
    "        to_ret = [-1 for _ in range(len(nums))]\n",
    "        for i, t in enumerate(nums) :\n",
    "            while len(heap_1) and heap_1[0][0] < t :\n",
    "                v, pv = heapq.heappop(heap_1)\n",
    "                to_ret[pv] = t\n",
    "            while len(heap_0) and heap_0[0][0] < t :\n",
    "                v, pv = heapq.heappop(heap_0)\n",
    "                heapq.heappush(heap_1, [v, pv])\n",
    "            \n",
    "            heapq.heappush(heap_0, [t, i])\n",
    "        return to_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = []\n",
    "        t = SortedList()\n",
    "        res = [-1]*n\n",
    "        for i in range(n):\n",
    "            while t and t[0][0] < nums[i]:\n",
    "                val,idx = t.pop(0)\n",
    "                res[idx] = nums[i]\n",
    "            while s and s[-1][0] < nums[i]:\n",
    "                t.add(s.pop())\n",
    "            s.append([nums[i],i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        m1 = []\n",
    "        m2 = []\n",
    "        res = [-1] * n\n",
    "        for i in range(n):\n",
    "            # print(m1, m2)\n",
    "            v = nums[i]\n",
    "            while m2 and v > m2[0][0]:\n",
    "                a = heapq.heappop(m2)\n",
    "                res[a[1]] = v\n",
    "            \n",
    "            while m1 and v > m1[0][0]:\n",
    "                a = heapq.heappop(m1)\n",
    "                heapq.heappush(m2, a)\n",
    "            \n",
    "            heapq.heappush(m1, (v, i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st1 = deque()\n",
    "        st2 = deque()\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while st2 and st2[-1][1] < x:\n",
    "                ans[st2.pop()[0]] = x\n",
    "                \n",
    "            tmp = []\n",
    "            while st1 and st1[-1][1] < x: \n",
    "                tmp.append(st1.pop())\n",
    "            size = len(tmp)\n",
    "            #print(tmp)\n",
    "            for j in range(size - 1, -1, -1):\n",
    "                st2.append(tmp[j])\n",
    "            st1.append((i, x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        st, pq, res = [], [], [-1] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while pq and pq[0][0] < num:\n",
    "                res[heapq.heappop(pq)[1]] = nums[i]\n",
    "            while st and st[-1][0] < num:\n",
    "                heapq.heappush(pq, st.pop())\n",
    "            st.append((num, i))\n",
    "            # print(pq1, pq2, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "\n",
    "        stk = []\n",
    "        stk2 = []\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            while stk and stk[-1][1] < num:\n",
    "                idx, n1 = stk.pop()\n",
    "                ans[idx] = num\n",
    "            \n",
    "            temp = []\n",
    "            while stk2 and stk2[-1][1] < num:\n",
    "                temp.append(stk2.pop())\n",
    "\n",
    "            stk2.append( (i, num) )\n",
    "            while temp:\n",
    "                stk.append(temp.pop())\n",
    "        \n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st = deque()\n",
    "        pq = []\n",
    "        ans = [-1] * len(nums)\n",
    "    \n",
    "        for i, val in enumerate(nums):\n",
    "            while pq and pq[0][0] < val:\n",
    "                ans[pq[0][1]] = val\n",
    "                heappop(pq)\n",
    "            while st and st[-1][0] < val:\n",
    "                heappush(pq, st.pop())\n",
    "            st.append((val, i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st=[]\n",
    "        st1=[]\n",
    "        res=[-1]*len(nums)\n",
    "        # print(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            # print(i,x)\n",
    "            while len(st1)>0 and st1[-1][1]<x:\n",
    "                # print(\" \",st1,st)\n",
    "                index=st1[-1][0]\n",
    "                res[index]=x\n",
    "                st1.pop(-1)\n",
    "            while len(st)>0 and st[-1][1]<x:\n",
    "                # print(st1,st)\n",
    "                index=bisect_left(st1, -st[-1][1], key=lambda x:-x[1])\n",
    "                st1.insert(index, st[-1])\n",
    "                st.pop(-1)\n",
    "            st.append((i,x))\n",
    "            # print(i,x,st1,st)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        st=[]\n",
    "        st1=[]\n",
    "        res=[-1]*len(nums)\n",
    "        # print(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            # print(i,x)\n",
    "            while len(st1)>0 and st1[-1][1]<x:\n",
    "                # print(\" \",st1,st)\n",
    "                index=st1[-1][0]\n",
    "                res[index]=x\n",
    "                st1.pop(-1)\n",
    "            tmp=[]\n",
    "            while len(st)>0 and st[-1][1]<x:\n",
    "                # print(st1,st)\n",
    "                # index=bisect_left(st1, -st[-1][1], key=lambda x:-x[1])\n",
    "                # st1.insert(index, st[-1])\n",
    "                tmp.append(st.pop(-1))\n",
    "            while tmp:\n",
    "                st1.append(tmp.pop(-1))\n",
    "            st.append((i,x))\n",
    "            # print(i,x,st1,st)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n \n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            tmp = []\n",
    "            while stack and nums[i] > stack[0][0]:\n",
    "                v, idx, times = heappop(stack)\n",
    "                if times == 1:\n",
    "                    res[idx] = nums[i]\n",
    "                else:\n",
    "                    tmp.append([v, idx, times + 1])\n",
    "            \n",
    "            for a in tmp:\n",
    "                heappush(stack, a)\n",
    "\n",
    "            heappush(stack, [nums[i], i,  0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]: \n",
    "        n = len(nums)\n",
    "        sorted_list = sorted(zip(range(n),nums),key=lambda x:-x[1] )\n",
    "        q = SortedList()\n",
    "        ans = [-1]*n  \n",
    "        for i in range(n): \n",
    "            idx = sorted_list[i][0]\n",
    "\n",
    "            temp =  q.bisect_left(idx)\n",
    "            q.add(idx)\n",
    "            if temp+2> len(q)-1 : \n",
    "                ans[idx] = -1\n",
    "            else:\n",
    "                ans[idx] = nums[ q[temp+2] ]  \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        \n",
    "        res = [-1 for _ in range(n)]\n",
    "        m1 = []\n",
    "        m0 = []\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            while m1 and m1[0][0] < nums[i]:\n",
    "                num, idx = heapq.heappop(m1)\n",
    "                res[idx] = nums[i]\n",
    "            while m0 and nums[m0[0][1]] < nums[i]:\n",
    "                num, idx = heapq.heappop(m0)\n",
    "                heapq.heappush(m1, (num, idx))\n",
    "            heapq.heappush(m0, (x, i))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        zero, one = [], []\n",
    "        res = [-1]*len(nums)\n",
    "        for i, e in enumerate(nums):\n",
    "            while one and one[-1][-1] < e:\n",
    "                ii, ee = one.pop()\n",
    "                res[ii] = e\n",
    "            temp = []\n",
    "            while zero and zero[-1][-1] < e:\n",
    "                temp.append(zero.pop())\n",
    "            one += reversed(temp)\n",
    "            zero.append((i, e))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        h0, h1 = [], []\n",
    "        res = [-1]*len(nums)\n",
    "        for j, n in enumerate(nums):\n",
    "            while h1 and h1[0][0] < n:\n",
    "                _, i = heappop(h1)\n",
    "                res[i] = n\n",
    "            while h0 and h0[0][0] < n:\n",
    "                heappush(h1, heappop(h0))\n",
    "            heappush(h0, (n, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            while arr2 and t > arr2[0][0]:\n",
    "                m, n = heappop(arr2)\n",
    "                res[n] = t\n",
    "            while arr1 and t > arr1[-1][0]:\n",
    "                heappush(arr2,arr1.pop())\n",
    "            arr1.append((t,i))        \n",
    "        return res           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack1, stack2 = [], []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack2 and stack2[0][0] < num:\n",
    "                _, idx = heapq.heappop(stack2)\n",
    "                ans[idx] = num\n",
    "\n",
    "            while stack1 and stack1[0][0] < num:\n",
    "                heapq.heappush(stack2, heapq.heappop(stack1))\n",
    "\n",
    "            heapq.heappush(stack1, (num, i))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        s = SortedList()\n",
    "        for _, i in sorted([(-x, i) for i, x in enumerate(nums)]):\n",
    "            j = s.bisect_right(i) + 1\n",
    "            if j < len(s):\n",
    "                ans[i] = nums[s[j]]\n",
    "            s.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1]*len(nums)\n",
    "        sl = SortedList()\n",
    "        for _, i in sorted([(-x, i) for i, x in enumerate(nums)]):\n",
    "            j = sl.bisect_right(i) + 1\n",
    "            if j < len(sl): ans[i] = nums[sl[j]]\n",
    "            sl.add(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        nex = [-1] * len(nums)\n",
    "        for i, n in enumerate(nums):\n",
    "            while s and s[-1][-1] < n:\n",
    "                nex[s[-1][0]] = i\n",
    "                s.pop()\n",
    "            s.append((i, n))\n",
    "        nexd = collections.defaultdict(list)\n",
    "        for i, j in enumerate(nex):\n",
    "            nexd[j].append(i)\n",
    "        h = []\n",
    "        prev_index = -1\n",
    "        ans = [-1] * len(nums)\n",
    "        # print(nexd)\n",
    "        for index in sorted(list(nexd.keys()))[1:]:\n",
    "            for j in range(prev_index + 1, index + 1):\n",
    "                while h and h[0][0] < nums[j]:\n",
    "                    ans[h[0][1]] = nums[j]\n",
    "                    heapq.heappop(h)\n",
    "            for i in nexd[index]:\n",
    "                heapq.heappush(h, (nums[i], i))\n",
    "            prev_index = index\n",
    "        for j in range(prev_index + 1, len(nums)):\n",
    "            while h and h[0][0] < nums[j]:\n",
    "                ans[h[0][1]] = nums[j]\n",
    "                heapq.heappop(h)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        ans, s, t = [], [], []\n",
    "        for num, v in enumerate(nums):\n",
    "            ans.append(-1)\n",
    "            while s and s[-1][1] < v:\n",
    "                ans[s[-1][0]] = v\n",
    "                s.pop()\n",
    "            mask = 0\n",
    "            i = -1\n",
    "            while t and t[i][1] < v:\n",
    "                mask -= 1\n",
    "                i -= 1\n",
    "                if -i > len(t):\n",
    "                    break\n",
    "            if i != -1:\n",
    "                s += t[mask:]\n",
    "                t = t[:mask]\n",
    "            t.append([num, v])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        mystack1 = []\n",
    "        mystack2 = []\n",
    "        tempstack = []\n",
    "        ans = [-1]*len(nums)\n",
    "        for p,i in enumerate(nums):\n",
    "            while mystack2 != []:\n",
    "                if i > mystack2[-1][0]:\n",
    "                    temp = mystack2.pop()\n",
    "                    ans[temp[1]] = i\n",
    "                else:\n",
    "                    break\n",
    "            while mystack1 != []:\n",
    "                if i > mystack1[-1][0]:\n",
    "                    tempstack.append(mystack1.pop())\n",
    "                else:\n",
    "                    break\n",
    "            while tempstack != []:\n",
    "                mystack2.append(tempstack.pop())\n",
    "            mystack1.append([i,p])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s1,ans,s2=[],[],[]\n",
    "        ans=[-1 for i in range(len(nums))]\n",
    "        ansdic={}\n",
    "        for i in range(len(nums)):\n",
    "            while s2!=[] and nums[i]>s2[-1][0]:\n",
    "                ans[s2.pop()[1]]=nums[i]\n",
    "            ls=[]\n",
    "            while s1!=[] and nums[i]>s1[-1][0]:\n",
    "                ls.append(s1.pop())\n",
    "            while ls!=[]:\n",
    "                s2.append(ls.pop())\n",
    "            s1.append([nums[i],i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        res=[-1]*len(nums)\n",
    "        st=SortedList()\n",
    "        k=2\n",
    "        a=sorted([-x,i] for i,x in enumerate(nums))\n",
    "        for _,i in a:\n",
    "            j=st.bisect_right(i)+k-1\n",
    "            if j<len(st):\n",
    "                res[i]=nums[st[j]]\n",
    "            st.add(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef secondGreaterElement(self, nums):\n",
    "\t\tn = len(nums)\n",
    "\t\tq0 = [[float('inf'), -1]]\n",
    "\t\tq1 = [[float('inf'), -1]]\n",
    "\t\tans = [-1] * n\n",
    "\t\tfor i, num in enumerate(nums):\n",
    "\t\t\twhile num > q1[0][0]:\n",
    "\t\t\t\tans[heapq.heappop(q1)[1]] = num\n",
    "\t\t\twhile num > q0[0][0]:\n",
    "\t\t\t\theapq.heappush(q1, heapq.heappop(q0))\n",
    "\t\t\theapq.heappush(q0, [num, i])\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList(key=lambda x: x[0])\n",
    "        ret = []\n",
    "        ansM = {}\n",
    "        for k, v in enumerate(nums):\n",
    "            idx1 = sd1.bisect_left((v, 0, k))\n",
    "            list2remove = []\n",
    "            list2add = []\n",
    "            for j in range(idx1):\n",
    "                if sd1[j][1] == 0:\n",
    "                    list2remove.append(sd1[j])\n",
    "                    list2add.append((sd1[j][0], v, sd1[j][2]))\n",
    "                else:\n",
    "                    list2remove.append(sd1[j])\n",
    "                    ansM[sd1[j][2]] = v\n",
    "            for i in list2remove:\n",
    "                sd1.remove(i)\n",
    "            for i in list2add:\n",
    "                sd1.add(i)\n",
    "            sd1.add((v, 0, k))\n",
    "        for k, v in enumerate(nums):\n",
    "            if k in ansM:\n",
    "                ret.append(ansM[k])\n",
    "            else:\n",
    "                ret.append(-1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.secondGreaterElement([2, 4, 0, 9, 6]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        m=len(nums)\n",
    "        N = m * 4\n",
    "        f = [0] * N\n",
    "\n",
    "        def build(k, l, r):\n",
    "            if l == r:\n",
    "                f[k] = nums[r-1]\n",
    "                return\n",
    "            mid = l + r >> 1\n",
    "            build(k << 1, l, mid)\n",
    "            build(k << 1 | 1, mid + 1, r)\n",
    "            f[k] = max(f[k << 1], f[k << 1 | 1])\n",
    "\n",
    "\n",
    "        # 建树\n",
    "        build(1, 1, m)\n",
    "        # stack=[]\n",
    "        # nt=[-1]*m\n",
    "        # for i,v in enumerate(nums):\n",
    "        #     while stack and nums[stack[-1]]<v:\n",
    "        #         index=stack.pop()\n",
    "        #         nt[index]=i\n",
    "        #     stack.append(i)\n",
    "        \n",
    "        \n",
    "        def query(k, l, r, x, y,v):\n",
    "            if f[k]<=v:return float('-inf')\n",
    "            if l==r:\n",
    "                return x\n",
    "            mid = l + r >> 1\n",
    "            if y <= mid:\n",
    "                return query(k << 1, l, mid, x, y,v)\n",
    "            elif x >= mid + 1:\n",
    "                return query(k << 1 | 1, mid + 1, r, x, y,v)\n",
    "            else:                \n",
    "                ans1=query(k << 1, l, mid, x, mid,v)\n",
    "                if ans1!=float('-inf'):\n",
    "                    return ans1\n",
    "                return query(k << 1 | 1, mid + 1, r, mid + 1, y,v)                \n",
    "               \n",
    "            \n",
    "            \n",
    "        res=[-1]*m\n",
    "        for i,v in enumerate(nums,start=1):\n",
    "            n1=query(1,1,m,i+1,m,v)\n",
    "            if n1==-inf or n1==m:continue\n",
    "            n2=query(1,1,m,n1+1,m,v)\n",
    "            if n2!=-inf:\n",
    "                res[i-1]=nums[n2-1]\n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "        \n",
    "        \n",
    "                    \n",
    "                \n",
    "            \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1] * len(nums)\n",
    "        s = SortedList()  # 名次数\n",
    "        for _, i in sorted((-x, i) for i, x in enumerate(nums)):\n",
    "            j = s.bisect_right(i) + 2 - 1\n",
    "            if j < len(s): ans[i] = nums[s[j]]\n",
    "            s.add(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:           \n",
    "        n = len(nums)\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        res = [-1 for _ in range(n)]\n",
    "        for i, nu in enumerate(nums):\n",
    "            if sl:\n",
    "                pos = sl.bisect_left([nu, 0, 0])\n",
    "                # print(\"pos \", pos)\n",
    "                for j in range(pos):\n",
    "                    # print(\"j \", j)\n",
    "                    # print(\"nu \", nu)\n",
    "                    if sl[j][0] < nu:\n",
    "                        sl[j][2] += 1\n",
    "                        if sl[j][2] == 2:\n",
    "                            res[sl[j][1]] = nu\n",
    "                rm = [sl[j] for j in range(pos) if sl[j][2] == 2]\n",
    "                for r in rm:\n",
    "                    sl.remove(r)\n",
    "            sl.add([nu, i, 0])\n",
    "            # print(sl)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        right = [[] for _ in range(n)]\n",
    "        sta = []\n",
    "        for i, x in reversed(list(enumerate(nums))):\n",
    "            while sta and x >= nums[sta[-1]]:\n",
    "                sta.pop()\n",
    "            if sta:\n",
    "                right[sta[-1]].append(i)\n",
    "            sta.append(i)\n",
    "        # print(right)\n",
    "        ans = [-1] * n\n",
    "        sta = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = nums[i]\n",
    "            lst = right[i]\n",
    "            if lst and sta:\n",
    "                for lidx in lst:\n",
    "                    l = 0\n",
    "                    r = len(sta)-1\n",
    "                    res = -1\n",
    "                    while l <= r:\n",
    "                        mid = (l + r) // 2\n",
    "                        if nums[sta[mid]] > nums[lidx]:\n",
    "                            res = mid\n",
    "                            l = mid + 1\n",
    "                        else:\n",
    "                            r = mid - 1\n",
    "                    if res >= 0 and nums[sta[res]] > nums[lidx]:\n",
    "                        ans[lidx] = nums[sta[res]]\n",
    "            while sta and x >= nums[sta[-1]]:\n",
    "                sta.pop()\n",
    "            sta.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        s1,ans=[],[]\n",
    "        s2=[]\n",
    "        ansdic={}\n",
    "        for i in range(len(nums)):\n",
    "            while s2!=[] and nums[i]>s2[-1][0]:\n",
    "                ansdic[s2.pop()[1]]=nums[i]\n",
    "            ls=[]\n",
    "            while s1!=[] and nums[i]>s1[-1][0]:\n",
    "                ls.append(s1.pop())\n",
    "            while ls!=[]:\n",
    "                s2.append(ls.pop())\n",
    "            s1.append([nums[i],i])\n",
    "        print(ansdic)\n",
    "        for i in range(len(nums)):\n",
    "            x=ansdic.get(i,-1)\n",
    "            ans.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        s = SortedList()\n",
    "        res = [-1] * n\n",
    "        for _, i in sorted((-x, i) for i, x in enumerate(nums)):\n",
    "            j = s.bisect_right(i) + 2 - 1\n",
    "            if j < len(s): res[i] = nums[s[j]]\n",
    "            s.add(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        data = [(-nums[idx], idx) for idx in range(len(nums))]\n",
    "        data.sort()\n",
    "        ans = [-1 for _ in range(len(nums))]\n",
    "        sl = SortedList()\n",
    "        for d in data:\n",
    "            v, pos = d[0], d[1]\n",
    "            t = sl.bisect_right(pos)\n",
    "            if t + 1 < len(sl):\n",
    "                ans[pos] = nums[sl[t + 1]]\n",
    "            sl.add(pos)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        a = sorted(zip(range(n), nums), key=lambda x: -x[1])\n",
    "        ans = [-1] * n\n",
    "        st = SortedList()\n",
    "        j = 0\n",
    "        for i, num in a:\n",
    "            while j < n and a[j][1] > num:\n",
    "                st.add(a[j][0])\n",
    "                j += 1\n",
    "            # print(i, num, st)\n",
    "            idx = st.bisect_right(i)\n",
    "            if idx + 1 < len(st):\n",
    "                ans[i] = nums[st[idx + 1]]\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
